import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
 * @author yu
 * @date 2025年05月XX日
 * @description 77. 组合
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 * */

public class _07_backtracking_01_77 {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) { // 终止条件
            result.add(new ArrayList<>(path));
            return;
        }
        //没有剪枝
        for (int i = startIndex; i <= n; i++) { // 单层递归逻辑
            path.add(i);
            backtracking(n, k, i + 1);
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        _07_backtracking_01_77 solution = new _07_backtracking_01_77();

        System.out.print("请输入 n 的值: ");
        int n = scanner.nextInt();

        System.out.print("请输入 k 的值: ");
        int k = scanner.nextInt();

        List<List<Integer>> combinations = solution.combine(n, k);

        System.out.println("从 1 到 " + n + " 中选取 " + k + " 个数的所有组合如下：");
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }

        scanner.close();
    }
}    